﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Sudoku
    {
        private bool findValue = false;
        private int[,] finishBoard = new int[9, 9];
        private int recuseveCount = 0;
        public Sudoku()
        {
            int[,] board = new int[9, 9];
            List<Unknown> unknownList = new List<Unknown>();
            
            //입력
            for (int i = 0; i < 9; i++)
            {
                string inputLine = GetConsole.GetString();
                for (int j = 0; j < 9; j++)
                {
                    int val = Int32.Parse(inputLine[j].ToString());
                    if (val == 0)
                    {
                        unknownList.Add(new Unknown(i, j));
                    }
                    board[i, j] = val;
                }
            }
            //1차 처리
            int valCount = ProcessBoard(unknownList, ref board);
            if (valCount > 0)
            {
                RecuseveProcess(unknownList, board);
            }
            else if (valCount < 0)
            {

            }
            else
            {
                finishBoard = board;
            }
            //출력
            Console.WriteLine("");
            for (int i = 0; i < 9; i++)
            {
                string result = string.Empty;
                for (int j = 0; j < 9; j++)
                {
                    result += finishBoard[i, j];
                }
                Console.WriteLine(result);
            }
            
        }
        private void RecuseveProcess(List<Unknown> takeUnknownList, int[,] takeBoard)
        {
            
            if (findValue)
            { return; }
            foreach (int val in takeUnknownList[0].SubValList)
            {
                recuseveCount++;
                int valCount = takeUnknownList.Sum(u => u.SubValCount);
                int[,] boardClon = (int[,])takeBoard.Clone();
                List<Unknown> unknownListClon = new List<Unknown>();
                foreach (Unknown unknown in takeUnknownList)
                {
                    Unknown newUnknown = new Unknown(unknown.X, unknown.Y, unknown.SubValList);
                    unknownListClon.Add(newUnknown);
                }
                boardClon[unknownListClon[0].X, unknownListClon[0].Y] = val;
                unknownListClon.RemoveAt(0);
                int subValCount = ProcessBoard(unknownListClon, ref boardClon);

                if (subValCount == 0)
                {
                    findValue = true;
                    finishBoard = boardClon;
                    return;
                }
                else if (subValCount < 0)
                {
                    continue;
                }
                else
                {
                    RecuseveProcess(unknownListClon, boardClon);
                }
            }
        }
        private int ProcessBoard(List<Unknown> unknownList, ref int[,] board)
        {
            int subValCount = 0;
            int beforeSubValCount = -1;
            while (subValCount != beforeSubValCount)
            {
                beforeSubValCount = subValCount;
                List<Unknown> unknownClon = new List<Unknown>(unknownList);
                subValCount = 0;
                foreach (Unknown unknown in unknownClon)
                {
                    if (unknown.CheckVal(ref board))
                    {
                        if (board[unknown.X, unknown.Y] == 0)
                        {
                            return -1;
                        }
                        else
                        {
                            unknownList.Remove(unknown);
                        }
                    }
                    else
                    {
                        subValCount += unknown.SubValCount;
                    }
                }
            }
            return subValCount;
        }
        struct Unknown
        {
            static private int[,] AREA = new int[3,2] { { 1, 2 }, { -1, 1 }, { -1, -2}};
            private int x;
            private int y;
            private List<int> subValList;
            public int X { get { return x; } }
            public int Y { get { return y; } }
            public int SubValCount { get { return subValList.Count; } }
            public List<int> SubValList { get { return subValList; } }
            public Unknown(int x, int y)
            {
                this.x = x;
                this.y = y;
                subValList = new List<int>(new int[]{1,2,3,4,5,6,7,8,9});
            }
            public Unknown(int x, int y, List<int> valList)
            {
                this.x = x;
                this.y = y;
                subValList = new List<int>(valList);
            }
            public void RemoveSubVal(int val)
            {
                subValList.Remove(val);
            }
            public bool AddSubVal(int val)
            {
                if (subValList.Contains(val))
                {
                    return false;
                }
                else
                {
                    subValList.Add(val);
                    return true;
                }
            }
            public bool CheckVal(ref int[,] board)
            {
                //X, Y축 검사
                for (int i = 0; i < 9; i++)
                {
                    if (subValList.Contains(board[i, y]))
                    {
                        subValList.Remove(board[i, y]);
                    }
                    if (subValList.Contains(board[x, i]))
                    {
                        subValList.Remove(board[x, i]);
                    }
                }
                //구역 검사
                int xArea = x % 3;
                int yArea = y % 3;
                if (subValList.Contains(board[x + AREA[xArea, 0], y + AREA[yArea, 0]]))
                {
                    subValList.Remove(board[x + AREA[xArea, 0], y + AREA[yArea, 0]]);
                }
                if (subValList.Contains(board[x + AREA[xArea, 1], y + AREA[yArea, 0]]))
                {
                    subValList.Remove(board[x + AREA[xArea, 1], y + AREA[yArea, 0]]);
                }
                if (subValList.Contains(board[x + AREA[xArea, 0], y + AREA[yArea, 1]]))
                {
                    subValList.Remove(board[x + AREA[xArea, 0], y + AREA[yArea, 1]]);
                }
                if (subValList.Contains(board[x + AREA[xArea, 1], y + AREA[yArea, 1]]))
                {
                    subValList.Remove(board[x + AREA[xArea, 1], y + AREA[yArea, 1]]);
                }

                if (subValList.Count == 1)
                {
                    board[x, y] = subValList[0];
                    return true;
                }
                else if (subValList.Count == 0)
                {
                    return true;
                }
                return false;
            }
        }
    }

}
